package thired.class17_bfprt;

public class Class02_ReservoirSampling {
    //1~N个数 最后选择k个返回数组 每个数等概率
    public static int[] randomGet(int N, int K){
        int[] res = new int[K];
        int index = 0;
        for (int i = 1; i <= N; i++) {
            if(i <= K){
                res[index++] = i;
            } else if(random(i) <= K) {
                 index = (int)(Math.random() * K);
                 res[index] = i;
            }

        }
        return res;
    }
    // 等概率返回1~i中的一个数字
    public static int random(int i) {
        return (int) (Math.random() * i) + 1;
    }

    public static void main(String[] args) {
        System.out.println("hello");
        int all = 100;
        int choose = 10;
        int testTimes = 50000;
        int[] counts = new int[all + 1];
        for (int i = 0; i < testTimes; i++) {
          int[] ans =  randomGet(all, choose);
            for (int j = 0; j < ans.length; j++) {
                counts[ans[j]]++;
            }
        }

        for (int i = 0; i < counts.length; i++) {
            System.out.println(i + " times : " + counts[i]);
        }
    }
}
